import java.util.*;

class Solution {
    public int lastRemaining(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        int last = 0;
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }

    /**
     * 超时
     *
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining2(int n, int m) {
        if (n < 1 || m < 1) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int cur = 0;
        while (list.size() > 1) {
            cur = (cur + m - 1) % n;
            list.remove(cur);
            n--;
        }
        return list.get(0);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int ans = s.lastRemaining(5, 3);
        System.out.println(ans);
        ans = s.lastRemaining(10, 17);
        System.out.println(ans);
    }
}